package leetcode_周赛._2022._202207;

import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

/**
 * @author yzh
 * @version 1.0
 * @date 2022/7/31 21:48
 * 304 周赛
 * AC3
 */
public class _31 {

    /**
     * 6132.使数组中所有元素都等于零
     * 算法：贪心
     *
     * @param nums
     * @return
     */
    public int minimumOperations(int[] nums) {
//        Arrays.sort(nums);
//        int ans = 0, idx = 0, len = nums.length;
//        while (idx < len && nums[idx] == 0) ++idx;
//        for (; idx < len; idx++) {
//            if (nums[idx] <= 0) continue;
//            ++ans;
//            for (int j = idx + 1; j < len; j++) nums[j] -= nums[idx];
//        }
//        return ans;
        // 从上面看出, 只要元素不小于 0 的, 都要需要操作
        Set<Integer> set = new HashSet<>();
        for (int num : nums) if (num != 0) set.add(num);
        return set.size();
    }

    /**
     * 6133.分组的最大数量
     * 算法：贪心
     *
     * @param grades
     * @return
     */
    public int maximumGroups(int[] grades) {
//        int len = grades.length;
//        if (len == 0) return 0;
//        Arrays.sort(grades);
//        int ans = 0, idx = 0, preVal = 0, preNum = 0;
//        while (idx < len) {
//            if (idx == 0) {
//                ++ans;
//                preVal = grades[idx++];
//                preNum = 1;
//                continue;
//            }
//            int val = 0, num = 0;
//            while (idx < len && (val <= preVal || num <= preNum)) {
//                val += grades[idx++];
//                ++num;
//            }
//            if (val > preVal && num > preNum) {
//                ++ans;
//                preVal = val;
//                preNum = num;
//            } else break;
//        }
//        return ans;
        // 从上面看出, 排序之后跟元素的值无关, 跟数组的长度有关
        int ans = 0, curLen = 1, sum = 0, len = grades.length;
        while (sum + curLen <= len) {
            ++ans;
            sum += curLen++;
        }
        return ans;
    }

    /**
     * 6134. 找到离给定两个节点最近的节点
     * 算法：图
     * 因为每个节点最多只有一条出边, 所以只有一条路走到头
     *
     * @param edges
     * @param node1
     * @param node2
     * @return
     */
    public int closestMeetingNode(int[] edges, int node1, int node2) {
        if (node1 == node2) return node1;
        int n = edges.length;
        int[] n1 = getDistance(edges, node1), n2 = getDistance(edges, node2);
        System.out.println(Arrays.toString(n1));
        System.out.println(Arrays.toString(n2));
        int ans = -1, min = n;
        for (int i = 0; i < n; i++) {
            int max = Math.max(n1[i], n2[i]);
            if (min > max) {
                ans = i;
                min = max;
            }
        }
        return ans;
    }

    int[] getDistance(int[] edges, int node) {
        int n = edges.length;
        int[] distance = new int[n];
        Arrays.fill(distance, n);
        int t = 0;
        for (; node != -1 && distance[node] == n; node = edges[node]) distance[node] = t++;
        return distance;
    }

}
